package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/">二叉树的最大深度(Maximum Depth of Binary Tree)</a>
 * <p>给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例1：
 *      输入：root = [3,9,20,null,null,15,7]
 *              3
 *             / \
 *            9   20
 *                / \
 *              15   7
 *      输出：3
 *
 * 示例2：
 *      输入：root = [1,null,2]
 *               1
 *                \
 *                 2
 *      输出：2
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中节点的数量在 [0, 10^4] 区间内。</li>
 *         <li>-100 <= Node.val <= 100</li>
 *     </ul>
 * </p>
 * @see LC0104DepthOfBinaryTree_S 二叉树的最大深度(Maximum Depth of Binary Tree)
 * @see LC0559MaximumDepthOfNaryTree_S N 叉树的最大深度(Maximum Depth of N-ary Tree)
 * @author c2b
 * @since 2023/5/11 11:36
 */
public class LC0104DepthOfBinaryTree_S {

    static class Solution {
        public int maxDepth(TreeNode root) {
            return maxDepthByIteration(root);
            //return maxDepthByRecursion(root);
        }

        /**
         * 递归。Math.max(左子树的高度，右子树的高度) + 1
         */
        private int maxDepthByRecursion(TreeNode node) {
            if (node == null) {
                return 0;
            }
            return Math.max(maxDepthByRecursion(node.left), maxDepthByRecursion(node.right)) + 1;
        }

        /**
         * 迭代。先把当前层的节点入队，弹出所有节点，将下一层的节点全部入队。
         */
        private int maxDepthByIteration(TreeNode node) {
            int maxDepth = 0;
            if (node == null) {
                return maxDepth;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(node);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode tempNode = queue.poll();
                    if (tempNode != null) {
                        if (tempNode.left != null) {
                            queue.offer(tempNode.left);
                        }
                        if (tempNode.right != null) {
                            queue.offer(tempNode.right);
                        }
                    }
                }
                ++maxDepth;
            }

            return maxDepth;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        System.out.println(solution.maxDepth(root1));
    }
}
